1. Field of the Invention
This invention relates generally to the field of computer graphics and, more particularly, to rendering polygons such as triangles.
2. Description of the Related Art
A computer system typically relies upon its graphics system for producing visual output on the computer screen or display device. Early graphics systems were only responsible for taking what the processor produced as output and displaying it on the screen. In essence, they acted as simple translators or interfaces. Modem graphics systems, however, incorporate graphics processors with a great deal of processing power. They now act more like coprocessors rather than simple translators. This change is due to the recent increase in both the complexity and amount of data being sent to the display device. For example, modern computer displays have many more pixels, greater color depth, and are able to display more complex images with higher refresh rates than earlier models. Similarly, the images displayed are now more complex and may involve advanced techniques such as anti-aliasing and texture mapping.
As a result, without considerable processing power in the graphics system, the CPU would spend a great deal of time performing graphics calculations. This could rob the computer system of the processing power needed for performing other tasks associated with program execution and thereby dramatically reduce overall system performance. With a powerful graphics system, however, when the CPU is instructed to draw a box on the screen, the CPU is freed from having to compute the position and color of each pixel. Instead, the CPU may send a request to the video card stating “draw a box at these coordinates.” The graphics system then draws the box, freeing the processor to perform other tasks.
Generally, a graphics system in a computer (also referred to as a graphics system) is a type of video adapter that contains its own processor to boost performance levels. These processors are specialized for computing graphical transformations, so they tend to achieve better results than the general-purpose CPU used by the computer system. In addition, they free up the computer's CPU to execute other commands while the graphics system is handling graphics computations. The popularity of graphical applications, and especially multimedia applications, has made high performance graphics systems a common feature of computer systems. Most computer manufacturers now bundle a high performance graphics system with their systems.
Since graphics systems typically perform only a limited set of functions, they may be customized and therefore far more efficient at graphics operations than the computer's general-purpose central processor. While early graphics systems were limited to performing two-dimensional (2D) graphics, their functionality has increased to support three-dimensional (3D) wire-frame graphics, 3D solids, and now includes support for three-dimensional (3D) graphics with textures and special effects such as advanced shading, fogging, alpha-blending, and specular highlighting.
A modern graphics system may generally operate as follows. First, graphics data is initially read from a computer system's main memory into the graphics system. The graphics data may include geometric primitives such as polygons (e.g., triangles), NURBS (Non-Uniform Rational B-Splines), sub-division surfaces, voxels (volume elements) and other types of data. The various types of data are typically converted into triangles (e.g., three vertices having at least position and color information). Then, transform and lighting calculation units receive and process the triangles. Transform calculations typically include changing a triangle's coordinate axis, while lighting calculations typically determine what effect, if any, lighting has on the color of triangle's vertices. The transformed and lit triangles may then be conveyed to a clip test/back face culling unit that determines which triangles are outside the current parameters for visibility (e.g., triangles that are off screen). These triangles are typically discarded to prevent additional system resources from being spent on non-visible triangles.
Next, the triangles that pass the clip test and back-face culling may be translated into screen space. The screen space triangles may then be forwarded to the set-up and draw processor for rasterization. Rasterization typically refers to the process of generating actual pixels (or samples) by interpolation from the vertices. The rendering process may include interpolating slopes of edges of the polygon or triangle, and then calculating pixels or samples on these edges based on these interpolated slopes. Pixels or samples may also be calculated in the interior of the polygon or triangle.
As noted above, in some cases samples are generated by the rasterization process instead of pixels. A pixel typically has a one-to-one correlation with the hardware pixels present in a display device, while samples are typically more numerous than the hardware pixel elements and need not have any direct correlation to the display device. Where pixels are generated, the pixels may be stored into a frame buffer, or possibly provided directly to refresh the display. Where samples are generated, the samples may be stored into a sample buffer or frame buffer. The samples may later be accessed and filtered to generate pixels, which may then be stored into a frame buffer, or the samples may possibly filtered to form pixels that are provided directly to refresh the display without any intervening frame buffer storage of the pixels.
The pixels are converted into an analog video signal by digital-to-analog converters. If samples are used, the samples may be read out of sample buffer or frame buffer and filtered to generate pixels, which may be stored and later conveyed to digital to analog converters. The video signal from converters is conveyed to a display device such as a computer monitor, LCD display, or projector.
As noted above, the rendering process may include interpolating slopes of edges of the polygon or triangle, and then calculating pixels or samples based on these interpolated slopes. One problem that arises is that a graphics system typically
When rasterizing a triangle, there are two major accumulations (or “walking”) required. The first accumulation (referred to as “edge walking”) comprises the “slicing” of the triangle into spans or slices while traversing an edge. The input to the edge walker or the first accumulator is the initial starting and ending points of the triangle and the slopes of each edge. While stepping along the edge, the edge walker generates the “slices” or “spans” which may be the start and end points for each slice (e.g., a scan line). These slices are the input to the second major accumulator, referred to as the “span walker”. The second accumulator or span walker “walks” the slice, generating the pixels that will eventually be stored in the frame buffer.
The size and shape of the triangle being rendered generally affects the work required to be performed by edge and span walkers. For example, if the triangle is mostly vertical, and if the first accumulator (edge walker) always accumulates left to right, then the second accumulator (span walker) will have a greater workload than the edge walker. This leaves the edge walker under utilized. If the triangle is mostly horizontal, then the edge walker will have an increased workload, but this increased workload may still be comparable to the span walker. This is because, in general, the span walking process is more time intensive than the edge walking process. Thus, with a random mixture of triangle shapes (including both horizontal and vertical triangles), the edge walker will typically be less utilized than the span walker.
Therefore, an improved system and method is desired for rendering polygons, such as triangles, with increased performance. A system and method is also desired for increasing the effective utilization of the span and edge walkers and removing bottlenecks in graphics rendering operations.